﻿using System;
using common;

namespace RemoveDuplicates
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            int[] arr = new int[] { 1, 1, 2 };
            int[] arr2 = new int[] { 0, 0, 1, 1, 1, 2, 2, 3, 3, 4 };
            System.Console.WriteLine(RemoveDuplicates3(arr));
            arr.Show();
            System.Console.WriteLine(RemoveDuplicates3(arr2));
            arr2.Show();
        }

        /*
        删除排序数组中的重复项
        给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

        不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

         

        示例 1:

        给定数组 nums = [1,1,2], 

        函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

        你不需要考虑数组中超出新长度后面的元素。
        示例 2:

        给定 nums = [0,0,1,1,1,2,2,3,3,4],

        函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

        你不需要考虑数组中超出新长度后面的元素。
         

        说明:

        为什么返回数值是整数，但输出的答案是数组呢?

        请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

        你可以想象内部操作如下:

        // nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
        int len = removeDuplicates(nums);

        // 在函数里修改输入数组对于调用者是可见的。
        // 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
        for (int i = 0; i < len; i++) {
            print(nums[i]);
        }

        作者：力扣 (LeetCode)
        链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2gy9m/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
        */
        public static int RemoveDuplicates(int[] nums)
        {
            if (nums?.Length <= 0) return 0;
            int temp = nums[0];
            int count = 1;
            for (int i = 1; i < nums.Length; i++)
            {
                if (nums[i] == temp)
                {
                    // check how many duplicates behind.
                    for (int j = i; j < nums.Length; j++)
                    {
                        if (nums[j] == nums[i])
                            continue;
                        // swap
                        temp = nums[j];
                        i = j;
                        nums[count++] = nums[j];
                        break;
                    }
                }
                else
                {
                    temp = nums[i];
                    nums[count++] = temp;
                }
            }
            return count;
        }

        /// <summary>
        /// 新建数组。空间复杂度O(n),时间复杂度O(n)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public static int RemoveDuplicates2(int[] nums)
        {
            if (nums?.Length <= 0) return 0;
            int count = 1;
            int[] arr = new int[nums.Length];
            arr[0] = nums[0];
            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i] == arr[count - 1])
                {
                    continue;
                }
                else
                {
                    arr[count++] = nums[i];
                }
            }
            for (int i = 0; i < count; i++)
            {
                nums[i] = arr[i];
            }
            return count;
        }

        // best !!!
        public static int RemoveDuplicates3(int[] nums)
        {
            if (nums?.Length <= 0) return 0;
            int count = 0;
            for (int i = 1; i < nums.Length; i++)
            {
                if (nums[count] != nums[i])
                {
                    count++;
                    nums[count] = nums[i];
                }
            }
            return count + 1;
        }


    }
}
